class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        return str1.substring(0, getHighestConventionNumber(str1.length(), str2.length()));
    }

    /**
     * 辗转相除法求最大公约数
     *
     * @param m
     * @param n
     * @return
     */
    public int getHighestConventionNumber(int m, int n) {
        if (m < n) {
            m = m ^ n;
            n = m ^ n;
            m = m ^ n;
        }
        if (m % n == 0) {
            return n;
        } else {
            return getHighestConventionNumber(n, m % n);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String res = solution.gcdOfStrings("ABABAB", "AB");
        //System.out.println(solution.getHighestConventionNumber(9, 6));
    }
}